package com.leetcode.www;

import java.util.LinkedList;
import java.util.Queue;

/**
 * Creared with IntelliJ IDEA.
 * Description:在给定的m x n网格grid中，每个单元格可以有以下三个值之一：
 *
 * 值0代表空单元格；
 * 值1代表新鲜橘子；
 * 值2代表腐烂的橘子。
 * 每分钟，腐烂的橘子周围4 个方向上相邻 的新鲜橘子都会腐烂。
 *
 * 返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回-1。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/rotting-oranges
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * User:yxd
 * Date:2022-03-19
 * Time:0:58
 */

public class BFS994 {
    public int[][] d = {{1,0},{-1,0},{0,1},{0,-1}};
    public int orangesRotting(int[][] grid) {
        if(grid == null)return 0;
        Queue<pair> queue = new LinkedList<>();
        int row = grid.length;
        int col = grid[0].length;
        for(int i = 0;i < row;i ++){
            for(int j = 0;j < col;j ++){
                if(grid[i][j] == 2){
                    queue.offer(new pair(i,j));
                }
            }
        }
        int count = 0;
        while(!queue.isEmpty()){
            int size = queue.size();
            boolean falg = false;
            while(size-- != 0){//所有腐烂的橘子
                pair p = queue.poll();//当前的腐烂的橘子
                for(int i = 0;i < 4;i ++){//四个方向
                    int nx = p.x + d[i][0];
                    int ny = p.y + d[i][1];
                    if(nx >= row || nx < 0
                            || ny >= col || ny < 0){//越界
                        continue;
                    }
                    if(grid[nx][ny] == 1){//是新鲜的橘子
                        falg = true;//这一步需要一分钟
                        grid[nx][ny] = 2;
                        queue.offer(new pair(nx,ny));//添加腐烂的橘子下一步看其周围的新鲜橘子
                    }

                }
            }
            if(falg){
                count++;
            }
        }
        for(int i = 0;i < row;i ++){
            for(int j = 0;j < col;j ++){
                if(grid[i][j] == 1){
                    return -1;
                }
            }
        }
        return count;
    }
}
